package com.sunny.l80;

public class Solution {

    public static void main(String[] args) {

        Solution solution = new Solution();
        System.out.println(solution.sqrt(4));

    }

    public int sqrt(int x) {

        int l = 0;
        int r = Integer.MAX_VALUE;
        int res = 0;

        while (l<r){
            int mid = l+((r-l)>>1);
//            System.out.println(l+" "+mid+" "+r);
            if(1l*mid*mid < x){
                if(1l*(mid+1)*(mid+1)>x){
                    res = mid;
                    break;
                }else if(1l*(mid+1)*(mid+1) == x){
                    res = mid+1;
                    break;
                }
                l = mid+1;
            }else if(1l*mid*mid > x){
                if(1l*(mid-1)*(mid-1)<=x){
                    res = mid-1;
                    break;
                }
                r = mid-1;
            }else{
                res = mid;
                break;
            }
        }

        return res;
    }
}
